package Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;

/**
 * https://leetcode-cn.com/problems/invert-binary-tree/
 * 翻转一棵二叉树。
 *
 * 示例：
 *
 * 输入：
 *
 *      4
 *    /   \
 *   2     7
 *  / \   / \
 * 1   3 6   9
 * 输出：
 *
 *      4
 *    /   \
 *   7     2
 *  / \   / \
 * 9   6 3   1
 */
public class L226_翻转二叉树 {
    /**
     * 这个叫层序遍历  也就是  宽度优先搜索算法（又称广度优先搜索） BFS
     */
    public TreeNode invertTree_层次遍历_非递归了(TreeNode root){
        if(root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//添加，相当于add，只是这个不抛异常

        while ( !queue.isEmpty() ){
            //获取后面获取节点
            TreeNode node = queue.poll();//poll 返回队首的元素，并删除
            //开始对本节点做操作
            TreeNode tmp = node.right;
            node.right = node.left;
            node.left = tmp;

            //开始处理这个节点的子节点
            if(node.right != null){
                queue.offer(node.right);
            }//处理左节点
            if(node.left != null){
                queue.offer(node.left);
            }
        }
        TreeSet<Integer> a = new TreeSet<>();
        a.add(1);
        return root;
    }

    //先序遍历
    public TreeNode invertTree_先序遍历(TreeNode root) {
        if(root == null) return null;
        //这里相当于本节点的代码处理
        TreeNode tmp = root.right;
        root.right = invertTree_先序遍历(root.left);
        root.left = invertTree_先序遍历(tmp);

        return root;
    }

    public TreeNode invertTree_中序遍历(TreeNode root) {
        if(root == null) return null;
        //先处理左边，处理本节点的代码在下面
        invertTree_中序遍历(root.left);

        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;
        //处理右边，因为已经交换了，所以，这里还是left
        invertTree_中序遍历(root.left);
        return root;
    }

    public TreeNode invertTree_后序遍历(TreeNode root){
        if(root == null) return null;
        //先处理左右，然后，再处理本节点
        invertTree_后序遍历(root.right);
        invertTree_后序遍历(root.left);
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;

        return root;
    }

}
